package dynamic;

import tree.TreeNode;
import java.util.*;

import org.junit.Test;

public class Ex337 {
    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(s.rob(null));
    }
    class Solution {
        //错误，少了一个状态，无法考虑到父节点有没有参与计算，我觉得可以升级[尝试了一波，发现仍然解决不了不知道上个节点偷窃路径的问题]
        public int robX(TreeNode root) {
            // int[] nums = getLevelNumbers(root);
            int[] nums = new int[]{3, 2, 3, -1, 3, -1, 1};
            int res = 0, len = nums.length, max, p;
            // int[] f = new int[len + 1];
            // f[0] = 0; //f[0] 表示一家都不打结
            int[][] f = new int[len][2]; //f[i][1] 表示只考虑前i + 1个数，选择打结第i家的情况下，最好的金额;f[i][0]表示不打结这家
            f[0][0] = 0;
            f[0][1] = nums[0];

            Set<Integer> set = new HashSet<>();
            for (int i = 1; i < len; i++) {
                if (nums[i] < 0) {
                    f[i][0] = -1;
                    f[i][1] = -1;
                    continue;
                } 
                int rob = 0, notRob = 0, rob2 = 0;
                for (int j = i - 1; j >= 0; j--) {
                    rob = Math.max(rob, f[j][1]);
                    if (j != (i - 1) / 2) rob2 = Math.max(rob2, f[j][1]);
                    notRob = Math.max(notRob, f[j][0]);
                }
                //1. 选择不打劫这家[从之前任何一家中选一个最大者]
                f[i][0] = Math.max(rob, notRob);
                //2.选择打结这家，则不能打劫他的父节点
                f[i][1] = Math.max(rob2, notRob);
                res = Math.max(res, Math.max(f[i][0], f[i][1]));
            }
            return res;
        }

        public int[] getLevelNumbers(TreeNode root) {

            TreeNode cur = root;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(cur);
            int high = getHeight(root), idx = 0, len = (1 << high) - 1;
            int[] res = new int[len];
            res[0] = cur.val;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                int left = idx * 2 + 1, right = idx * 2 + 2;
                if (cur.left != null) {
                   res[left] = cur.left.val;
                    queue.offer(cur.left);
                } else if (left < len) res[left] = -1; //add -1使得不会遍历这个位置

                if (cur.right != null) {
                    res[right] = cur.right.val;
                    queue.offer(cur.right);
                } else if (right < len) res[right] = -1; //add -1使得不会遍历这个位置
                idx++;
            }
            return res;
        }

        public int getHeight(TreeNode root) {
            if (root == null) return 0;
            return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
        }


            Map<TreeNode, Integer> map = new HashMap<>(); //记忆化递归
            public int rob(TreeNode root) {
                if (root == null) {
                    return 0;
                }
                if (map.containsKey(root)) return map.get(root);
                int notRob = rob(root.left) + rob(root.right); //不强当前节点，就可以抢其左子树和右子树
                //选择抢了当前的节点，则其左子树和右子树不能抢
                int rob = root.val;
                if (root.left != null) rob += (rob(root.left.left) + rob(root.left.right));
                if (root.right != null) rob += (rob(root.right.left) + rob(root.right.right));
                int res = Math.max(notRob, rob);
                map.put(root, res);
                return res; //抢或者不抢选择较大者
            }
    }

    class Solution2 {
         public int rob(TreeNode root) {
            int[] cur = postOrder(root);
            return Math.max(cur[0], cur[1]); 
         }

         public int[] postOrder(TreeNode root) {
            if (root == null) {
                return new int[] {0, 0};
            }
            int[] left = postOrder(root.left), right = postOrder(root.right), cur = new int[2];
            cur[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
            cur[1] = root.val + left[0] + right[0];
            return cur;
         }
  }

  @Test
  public void test2() {
    //   [3,2,3,null,3,null,1]
    TreeNode root = new TreeNode(3), cur = root;
    cur.left = new TreeNode(2);
    cur.right =new TreeNode(3);
    cur = cur.left;
    cur.right = new TreeNode(3);
    cur = root.right;
    cur.right = new TreeNode(1);

    Solution2 s = new Solution2();
    int res = s.rob(root);
    System.out.println(res);
  }
}
